/*
 * @Descripttion: 
 * @version: 
 * @Author: lily
 * @Date: 2021-04-01 10:24:46
 * @LastEditors: lily
 * @LastEditTime: 2021-04-01 11:23:51
 */
/*
 * @lc app=leetcode.cn id=198 lang=javascript
 *
 * [198] 打家劫舍
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number}
 */


//  思路： 
//  dp[j] 表示从 0 到 j 能偷盗的最大值       
//  dp[j] = Math.max(dp[j - 2] + nums[j], dp[j - 1])  即第j间偷不偷看到前一间投的多还是到前两间加上j偷的多

//  复杂度：O(n)、O(1) => 滚动数组，只存储前两间房屋的最高总金额

var rob = function (nums) {
    let n = nums.length
    let dp = new Array(n).fill(0)
    for (let i = 0; i < n; i++) {
        for (let j = i; j < n; j++) {
            // 初始值 dp[j]表示从0到j能偷盗的最大值
            if (j - i < 2) {
                dp[j] = Math.max(nums[i], nums[j])
            } else {
                dp[j] = Math.max(dp[j - 2] + nums[j], dp[j - 1])
            }
        }
        return dp[n - 1]
    }

};
// @lc code=end

console.log(rob([2, 7, 9, 3, 1]));